package com.qjc.demo.train.half;

/**
 * @ClassName: HalfDemo3 阿里面试题
 * @Description:一个有序数组有一个数出现1次，其他数出现2次，找出出现一次的数 比如：1 1 2 2 3 3 4 4 5 5 6 6 7 出现1次的数是7
 * @Author: qjc
 * @Date: 2022/5/1 1:56 PM
 */
public class HalfDemo3Interview {
    // 核心
    // 偶数位索引跟后面的比相同，奇数位索引跟前面的比相同 则说明前面的都对
    // 偶数位索引跟前面的比相同，奇数位索引跟后面的比相同 则说明后面的都对
    public static int binarySearch(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        int mid = 0;
        while (low < high) {
            mid = (low + high) / 2;
            // 偶数位
            if (mid % 2 == 0) {
                if (nums[mid] == nums[mid + 1]) {
                    // 与后面的数相等，前面的都对
                    low = mid + 1;
                } else if (nums[mid] == nums[mid - 1]) {
                    // 与前面的数相等，后面的都对
                    high = mid - 1;
                } else {
                    return nums[mid];
                }
            } else {
                // 奇数位
                if (nums[mid] == nums[mid + 1]) {
                    // 与后面的数相等，后面的都对
                    high = mid - 1;
                } else if (nums[mid] == nums[mid - 1]) {
                    // 与前面的数相等，前面的都对
                    low = mid + 1;
                } else {
                    return nums[mid];
                }
            }
        }
        return nums[low];
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 2, 3, 4, 4, 5, 5};
        System.out.println(binarySearch(nums));
    }

}
